﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.IO;

namespace OCRTheNewHope
{
    class DecisionNode
    {
        public int NodeID { get; set; }
        public static int CurrentGlobalLevel = 0;

        static int[][] refineOffsets = {
                                new int[] {0,-1},
                                new int[] {-1,0},
                                new int[] {0, 1},
                                new int[] {1, 0},
                                new int[] {0,0}
                              };

        public DecisionTree Owner { get; private set; }
        public DecisionNode Parent { get; private set; }
        public Digit[] Inputs { get; private set; }
       
        public int? Output { get; private set; }
        
        public int Level { get; private set; }
        public Feature SplitFeature { get; set; }
        public DecisionNode[] Branches { get; private set; }

        public bool IsRoot
        {
            get { return Parent == null; }
        }

        public bool IsLeaf
        {
            get { return Branches == null || Branches.Length == 0; }
        }

        public DecisionNode(DecisionTree owner, DecisionNode parent, Digit[] inputs)
        {
            this.Owner = owner;
            this.Parent = parent;
            this.Inputs = inputs;

            if (IsRoot)
                this.Level = 0;
            else
                this.Level = this.Parent.Level + 1;

            if (this.Level > DecisionNode.CurrentGlobalLevel)
            {
                Console.WriteLine(this.Level);
                DecisionNode.CurrentGlobalLevel = this.Level;
            }
        }

        private Feature[] CreateRefineFeatureCandidates()
        {
            Feature[] rVal = new Feature[Parameters.UsedFeatureCountAtEveryNode];

            for (int idx = 0; idx < rVal.Length / 2; idx++)
                rVal[idx] = new Feature(RectangleType.Normal);

            for (int idx = rVal.Length / 2; idx < rVal.Length ; idx++)
                rVal[idx] = new Feature(RectangleType.Rotated);

            return rVal;
        }

        public Feature GetBestFeature(Feature[] featureCandidates, out Digit[][] bestPartition, double entropy)
        {
            Digit[][] tempPartition;

            tempPartition = new Digit[2][];
            bestPartition = new Digit[2][];
            double entropyGain = 0;

            int bestAttributeIndex;
            double bestGain;

            bestGain = 0;
            bestAttributeIndex = 0;

            for (int i = 0; i < featureCandidates.Length; i++)
            {
                entropyGain = ComputeGainRatio(this.Inputs, featureCandidates[i], out tempPartition, entropy);

                if (entropyGain > bestGain)
                {
                    bestAttributeIndex = i;
                    bestGain = entropyGain;
                    featureCandidates[i].EntropyGain = entropyGain;

                    bestPartition[0] = tempPartition[0].ToArray();
                    bestPartition[1] = tempPartition[1].ToArray();

                    tempPartition[0] = null;
                    tempPartition[1] = null;
                }
            }

            return featureCandidates[bestAttributeIndex];
        }

        public Feature[] CreateFeatureCandidates(Feature f)
        {
            Feature[] rVal = new Feature[refineOffsets.Length * refineOffsets.Length];

            int index = 0;
            for (int i = 0; i < refineOffsets.Length; i++)
            {
                for (int j = 0; j < refineOffsets.Length; j++)
                {
                    Point p1 = new Point(f.Rectangle0.A.X + refineOffsets[i][0],f.Rectangle0.A.Y + refineOffsets[i][1]);
                    Point p2 = new Point(f.Rectangle0.D.X + refineOffsets[j][0], f.Rectangle0.D.Y + refineOffsets[j][1]);
                    
                    rVal[index] = new Feature(p1, p2);

                    index++;
                }
            }

            return rVal;
        }

        public DecisionNode[] Split()
        {
            Digit[][] bestPartition;
            double bestGain = 0;
            Feature[] featureCandidates;
           
            double entropy = Entropy(this.Inputs);
            
            if (this.Level > Parameters.MaxDepth)
            {
                TerminateNode();
                return null;
            }

            int counter = 0;
            do
            {
                featureCandidates = CreateRefineFeatureCandidates();

                this.SplitFeature = GetBestFeature(featureCandidates, out bestPartition, entropy);

                bestGain = this.SplitFeature.EntropyGain;

                counter++;
            }
            while (!(bestGain > 4 * Parameters.EntropyThreshold) && counter < 4);

            if (!(bestGain > 0))
            {
                TerminateNode();
                return null;
            }

            Feature[] newFeatures;
            Feature newBestFeature;
            Digit[][] newBestPartition;
            bool loop = true;
            int refineCounter = 0;
            
            while(loop) // refine loop
            {
                newFeatures = CreateFeatureCandidates(this.SplitFeature);
                newBestFeature = GetBestFeature(newFeatures, out newBestPartition, entropy);

                if (newBestFeature.EntropyGain > this.SplitFeature.EntropyGain)
                {
                    this.SplitFeature = newBestFeature;
                    bestPartition = newBestPartition;
                    loop = true;
                }
                else
                {
                    loop = false;
                }

                refineCounter++;

                if (refineCounter > 2)
                {
                    loop = false;
                }
            }
                        
            this.Branches = new DecisionNode[2];

            this.Branches[0] = new DecisionNode(this.Owner, this, bestPartition[0]);
            this.Branches[1] = new DecisionNode(this.Owner, this, bestPartition[1]);

            if (this.Level < 8)
            {
                CreateNodeImage();
            }

            this.Inputs = null;

            return this.Branches;
        }

        private void CreateNodeImage()
        {
            double[,] accumulativeMatrix = new double[28, 28];
            for (int i = 0; i < this.Inputs.Length; i++)
            {
                accumulativeMatrix.Add(this.Inputs[i].OriginalGrayscaleMatrix);
            }

            for (int i = 0; i < accumulativeMatrix.GetLength(0); i++)
            {
                for (int j = 0; j < accumulativeMatrix.GetLength(1); j++)
                {
                    accumulativeMatrix[i, j] /= this.Inputs.Length;
                }
            }

            Bitmap bmp = Visualizer.Visualize(accumulativeMatrix, this.SplitFeature.Rectangle0);

            if (!Directory.Exists(Parameters.GlobalImagePath))
                Directory.CreateDirectory(Parameters.GlobalImagePath);

            string path = Parameters.GlobalImagePath + "\\" + this.Owner + "_Level_" + this.Level + "_NodeID_" + this.NodeID + "_NumberOfItems_" + this.Inputs.Length + ".png";
            
            bmp.Save(path);
        }

        private void TerminateNode()
        {
            this.Output = MostCommon(this.Inputs);
            this.Inputs = null;        
        }

        private int MostCommon(Digit[] digits)
        {
            int[] frequencies = new int[10];

            for (int i = 0; i < digits.Length; i++)
                frequencies[digits[i].DigitValue]++;

            return frequencies.MaxIndex();
        }

        public double ComputeGainRatio(Digit[] digits, Feature feature, out Digit[][] partitions, double currentEntropy)
        {
            double infoGain = currentEntropy - ComputeInfo(digits, feature, out partitions);

            return infoGain;
        }

        public double ComputeInfo(Digit[] digits, Feature feature, out Digit[][] bestPartitions)
        {
            bool[][] digitFeatureArray = new bool[digits.Length][];

            Digit[][] tempPartitions = new Digit[2][];
            bestPartitions = new Digit[2][];
         
            List<Digit> tempPartitions0 = new List<Digit>(digits.Length);
            List<Digit> tempPartitions1 = new List<Digit>(digits.Length);

            for (int i = 0; i < digits.Length; i++)
            {
                digitFeatureArray[i] = digits[i].ComputeFeature(feature); // false is left, true is right
            }

            double bestEntropy = Parameters.MaxEntropy;
        
            for (int i = 0; i < Parameters.NumberOfThresholds; i++)
            {
                tempPartitions0.Clear();
                tempPartitions1.Clear();

                for (int d = 0; d < digits.Length; d++)
                {
                    if (digitFeatureArray[d][i] == false)
                        tempPartitions0.Add(digits[d]);
                    else
                        tempPartitions1.Add(digits[d]);
                }

                tempPartitions[0] = tempPartitions0.ToArray();
                tempPartitions[1] = tempPartitions1.ToArray();

                // Compute the information gain obtained by using
                // this current attribute as the next decision node.
                double entropy = 0;

                for (int p = 0; p < tempPartitions.Length; p++)
                {
                    double e = Entropy(tempPartitions[p]);
                    entropy += ((double)tempPartitions[p].Length / this.Inputs.Length) * e;
                }

                if (entropy < bestEntropy)
                {
                    bestEntropy = entropy;
                    feature.SetThreshold(i);
                    bestPartitions[0] = tempPartitions0.ToArray();
                    bestPartitions[1] = tempPartitions1.ToArray();
                }
            }

            feature.ThresholdCandidates = null;

            return bestEntropy;
        }

        public static double Entropy(Digit[] digits)
        {
            if (digits.Length == 0)
                return 0;

            int[] frequencies = new int[10];
            double[] p = new double[10];

            for (int i = 0; i < digits.Length; i++)
                frequencies[digits[i].DigitValue]++;

            for (int i = 0; i < frequencies.Length; i++)
                p[i] = (double)frequencies[i] / digits.Length;

            double sum = 0;
            for (int i = 0; i < p.Length; i++)
                if (p[i] != 0) sum += p[i] * Math.Log(p[i], 2);

            return -1 * sum;
        }

        public static double SplitInformation(Digit[][] partitions, int numTotalRecords)
        {
            double info = 0;

            for (int i = 0; i < partitions.Length; i++)
            {
                double p = (double)partitions[i].Length / numTotalRecords;
                if (p != 0)
                    info -= p * Math.Log(p, 2);
            }

            return info;
        }

        public DecisionNode PassToChild(Digit p)
        {
            bool temp = p.ComputeTestFeature(this.SplitFeature);

            if (temp == false)
                return this.Branches[0];
            return this.Branches[1];
        }

        public double[] GetHistogram(Digit[] inputs)
        {
            double[] rVal = new double[10];

            for (int i = 0; i < inputs.Length; i++)
            {
                rVal[inputs[i].DigitValue]++;
            }

            for (int i = 0; i < rVal.Length; i++)
            {
                rVal[i] = rVal[i] / inputs.Length;
            }

            return rVal;
        }
    }
}
